home *** CD-ROM | disk | FTP | other *** search
/ IRIX Base Documentation 2002 November / SGI IRIX Base Documentation 2002 November.iso / usr / share / catman / p_man / cat3 / SCSL / intro_fft.z / intro_fft
Encoding:
Text File  |  2002-10-03  |  32.6 KB  |  661 lines

  1.  
  2.  
  3.  
  4. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  5.  
  6.  
  7.  
  8. NNNNAAAAMMMMEEEE
  9.      IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT - Introduction to signal processing routines
  10.  
  11. IIIIMMMMPPPPLLLLEEEEMMMMEEEENNNNTTTTAAAATTTTIIIIOOOONNNN
  12.      See individual man pages for operating system and hardware availability
  13.  
  14. DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  15.      The signal processing routines currently consist of Fast Fourier
  16.      Transform (FFT) routines, convolution routines, and correlation routines.
  17.  
  18.      The following data types are used in these routines:
  19.  
  20.      *   Single precision: Fortran "real" data type, C/C++ "float" data type,
  21.          32-bit floating point; these routine names begin with SSSS.
  22.  
  23.      *   Single precision complex: Fortran "complex" data type, C/C++
  24.          "scsl_complex" data type (defined in <<<<ssssccccssssllll____fffffffftttt....hhhh>>>>), C++ STL
  25.          "complex<float>" data type (defined in <<<<ccccoooommmmpppplllleeeexxxx....hhhh>, two 32-bit
  26.          floating point reals; these routine names begin with CCCC.
  27.  
  28.      *   Double precision: Fortran "double precision" data type, C/C++
  29.          "double" data type, 64-bit floating point; these routine names begin
  30.          with DDDD.
  31.  
  32.      *   Double precision complex: Fortran "double complex" data type, C/C++
  33.          "scsl_zomplex" data type (defined in <<<<ssssccccssssllll____fffffffftttt....hhhh>>>>), C++ STL
  34.          "complex<double>" data type (defined in <<<<ccccoooommmmpppplllleeeexxxx....hhhh>>>>), two 64-bit
  35.          floating point doubles; these routine names begin with ZZZZ.
  36.  
  37.      NOTE: when using the C++ Standard Template Library (STL) to define
  38.      complex types, the include files must be used in the following order:
  39.  
  40.           #include <complex.h>
  41.           #include <scsl_fft.h>
  42.  
  43.  
  44.      Often little or no difference exists between these versions, other than
  45.      the data types of some inputs and outputs.  In this case, the routines
  46.      are described on the same man page, and that man page is named after the
  47.      real or complex routine.
  48.  
  49.      The mmmmaaaannnn(1) command can find a man page online by either the real,
  50.      complex, double precision, or double complex name.
  51.  
  52.      The data types for the _s_c_a_l_e, _t_a_b_l_e, and _w_o_r_k arguments in these routines
  53.      vary, depending on the function which is called.  In the CCCCCCCC, SSSSCCCC, and CCCCSSSS
  54.      routines, the arguments are single precision.  In the ZZZZZZZZ, DDDDZZZZ and ZZZZDDDD
  55.      routines, the arguments are double precision.
  56.  
  57.      By default, the integer arguments are 4 bytes (32 bits) in size; this is
  58.      the size obtained when one links to the SCSL library with ----llllssssccccssss or
  59.      ----llllssssccccssss____mmmmpppp. Another version of SCSL is available, however, in which
  60.  
  61.  
  62.  
  63.                                                                         PPPPaaaaggggeeee 1111
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  71.  
  72.  
  73.  
  74.      integers are 8 bytes (64 bits).  This version allows the user access to
  75.      larger memory sizes and helps when porting legacy Cray codes.  It can be
  76.      loaded by using either the ----llllssssccccssss____iiii8888 or ----llllssssccccssss____iiii8888____mmmmpppp link option.  Note
  77.      that any program may use only one of the two versions; 4-byte integer and
  78.      8-byte integer library calls cannot be mixed.
  79.  
  80.      C/C++ function prototypes for the signal processing routines are provided
  81.      in <<<<ssssccccssssllll____fffffffftttt....hhhh>>>>, when using the default 4-byte integers, and
  82.      <<<<ssssccccssssllll____fffffffftttt____iiii8888....hhhh>>>>, when using 8-byte integers. These header files define
  83.      the complex types ssssccccssssllll____ccccoooommmmpppplllleeeexxxx and ssssccccssssllll____zzzzoooommmmpppplllleeeexxxx, which are used in the
  84.      prototypes. Alternatively, C++ programs may declare arguments using the
  85.      types ccccoooommmmpppplllleeeexxxx<<<<ffffllllooooaaaatttt>>>> and ccccoooommmmpppplllleeeexxxx<<<<ddddoooouuuubbbblllleeee>>>> from the standard template
  86.      library. But if these types are used, <<<<ccccoooommmmpppplllleeeexxxx....hhhh>>>> must be included before
  87.      <<<<ssssccccssssllll____fffffffftttt....hhhh>>>> (or <<<<ssssccccssssllll____fffffffftttt____iiii8888....hhhh>>>>). Note, though, that both complex types
  88.      are equivalent: they simply represent (real, imaginary) pairs of floating
  89.      point numbers stored contiguously in memory. With the proper casts, you
  90.      can simply pass arrays of floating point data to the routines where
  91.      complex arguments are expected.
  92.  
  93.      Casts, however, can be avoided. The header files <<<<ssssccccssssllll____fffffffftttt....hhhh>>>> and
  94.      <<<<ssssccccssssllll____fffffffftttt____iiii8888....hhhh>>>> directly support the use of user-defined complex types or
  95.      disabling prototype checking for complex arguments completely.  By
  96.      defining the symbol SSSSCCCCSSSSLLLL____VVVVOOOOIIIIDDDD____AAAARRRRGGGGSSSS before including <<<<ssssccccssssllll____fffffffftttt....hhhh>>>> or
  97.      <<<<ssssccccssssllll____fffffffftttt____iiii8888....hhhh>>>> all complex arguments will be prototyped as vvvvooooiiiidddd ****. To
  98.      define the symbol SSSSCCCCSSSSLLLL____VVVVOOOOIIIIDDDD____AAAARRRRGGGGSSSS at compile time use the ----DDDD compiler
  99.      option (i.e., ----DDDDSSSSCCCCSSSSLLLL____VVVVOOOOIIIIDDDD____AAAARRRRGGGGSSSS) or use an explicit ####ddddeeeeffffiiiinnnneeee SSSSCCCCSSSSLLLL____VVVVOOOOIIIIDDDD____AAAARRRRGGGGSSSS
  100.      in the source code.  This allows the use of any complex data structure
  101.      without warnings from the compiler, provided the structure is as
  102.      described above; that is:
  103.  
  104.      1.   The real and imaginary components must be contiguous in memory.
  105.  
  106.      2.   Sequential array elements must also be contiguous in memory.
  107.  
  108.      While this allows the use of non-standard complex types without
  109.      generating compiler warnings, it has the disadvantage that the compiler
  110.      will not catch type mismatches.
  111.  
  112.      Strong type checking can be enabled employing user-defined complex types
  113.      instead of SCSL's standard complex types. To do this, define
  114.      SSSSCCCCSSSSLLLL____UUUUSSSSEEEERRRR____CCCCOOOOMMMMPPPPLLLLEEEEXXXX____TTTT====_m_y__c_o_m_p_l_e_x and SSSSCCCCSSSSLLLL____UUUUSSSSEEEERRRR____ZZZZOOOOMMMMPPPPLLLLEEEEXXXX____TTTT====_m_y__z_o_m_p_l_e_x, where
  115.      _m_y__c_o_m_p_l_e_x and _m_y__z_o_m_p_l_e_x are the names of user-defined complex types.
  116.      These complex types must be defined before including the <<<<ssssccccssssllll____fffffffftttt....hhhh>>>> (or
  117.      <<<<ssssccccssssllll____fffffffftttt____iiii8888....hhhh>>>>) header file.
  118.  
  119.      Fortran 90 users on IRIX systems can perform compile-time checking of
  120.      SCSL FFT subroutine calls by adding UUUUSSSSEEEE SSSSCCCCSSSSLLLL____FFFFFFFFTTTT (for 4-byte integer
  121.      arguments) or UUUUSSSSEEEE SSSSCCCCSSSSLLLL____FFFFFFFFTTTT____IIII8888 (for 8-byte integer arguments) to the
  122.      source code from which the FFT calls are made.  Alternatively, the
  123.      compile-time checking can be invoked without any source code
  124.      modifications by using the ----aaaauuuuttttoooo____uuuusssseeee compiler option, e.g.,
  125.  
  126.  
  127.  
  128.  
  129.                                                                         PPPPaaaaggggeeee 2222
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  137.  
  138.  
  139.  
  140.           f90 -auto_use SCSL_FFT test.f -lscs
  141.           f90 -auto_use SCSL_FFT_I8 -i8 test.f -lscs_i8
  142.  
  143.  
  144. FFFFFFFFTTTT rrrroooouuuuttttiiiinnnneeeessss
  145.      These routines apply to one or more FFTs.
  146.  
  147.      Following is a table of supported FFT routines.  Each of these routines
  148.      is highly optimized for single-processor use.  The two-dimensional,
  149.      three-dimensional, and one-dimensional multiple routines are also
  150.      multitasked (multi-threaded) for all sizes for which there is a
  151.      performance benefit; the one-dimensional routines are multitasked if the
  152.      data size exceeds the size of the largest processor cache. Each routine
  153.      can compute either a forward or an inverse Fourier transform.
  154.  
  155.      In this table, rows of the table represent input and output data types
  156.      for the routines in each column.:
  157.  
  158.      *   CCCC---->>>>CCCC implies 32-bit complex input and output.
  159.  
  160.      *   ZZZZ---->>>>ZZZZ implies 64-bit double complex input and 64-bit double complex
  161.          output.  Each routine in this row is documented with the complex
  162.          routine in the above row.
  163.  
  164.      *   SSSS---->>>>CCCC implies 32-bit real input and 32-bit complex output.
  165.  
  166.      *   DDDD---->>>>ZZZZ implies 64-bit double precision real input and 64-bit double
  167.          precision complex output.  Each routine in this row is documented
  168.          with the real-to-complex routine in the above row.
  169.  
  170.      *   CCCC---->>>>SSSS implies 32-bit complex input and 32-bit real output.
  171.  
  172.      *   ZZZZ---->>>>DDDD implies 64-bit double complex input and 64-bit double precision
  173.          output.  Each routine named in this row is documented with the
  174.          complex - real routine in the above row.
  175.  
  176.      Columns of the table represent the number of dimensions for which the FFT
  177.      is calculated for the routines in each row:
  178.  
  179.      *   One-dimensional (single) calculates one FFT in one dimension.
  180.  
  181.      *   One-dimensional (multiple) calculates an FFT in one dimension for
  182.          each column of a two-dimensional matrix.
  183.  
  184.      *   Two-dimensional calculates one FFT in two dimensions.
  185.  
  186.      *   Three-dimensional calculates one FFT in three dimensions.
  187.  
  188.      ---------------------------------------------------------------------------
  189.              1-dimensional        1-dimensional       2-dimensional 3-dimensional
  190.                (single)            (multiple)
  191.      ---------------------------------------------------------------------------
  192.  
  193.  
  194.  
  195.                                                                         PPPPaaaaggggeeee 3333
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  203.  
  204.  
  205.  
  206.      C->C       CCFFT         CCFFTM       CCFFTMR       CCFFT2D      CCFFT3D
  207.  
  208.      Z->Z       ZZFFT         ZZFFTM       ZZFFTMR       ZZFFT2D      ZZFFT3D
  209.  
  210.      S->C       SCFFT         SCFFTM                     SCFFT2D      SCFFT3D
  211.  
  212.      D->Z       DZFFT         DZFFTM                     DZFFT2D      DZFFT3D
  213.  
  214.      C->S       CSFFT         CSFFTM                     CSFFT2D      CSFFT3D
  215.  
  216.      Z->D       ZDFFT         ZDFFTM                     ZDFFT2D      ZDFFT3D
  217.      ---------------------------------------------------------------------------
  218.  
  219.  
  220. NNNNOOOOTTTTEEEESSSS
  221.      The FFT routines were designed so that they can be implemented
  222.      efficiently on many different architectures.  The calling sequence is the
  223.      same in any implementation.  Certain details, however, depend on the
  224.      particular implementation.
  225.  
  226.      One area of difference is the size of the _t_a_b_l_e and _w_o_r_k arrays.
  227.      Different systems may need different sizes.  The subroutine call requires
  228.      no change, but you may have to change array sizes in the DDDDIIIIMMMMEEEENNNNSSSSIIIIOOOONNNN or
  229.      type statements that declare the arrays. The following are the required
  230.      array sizes for the Origin series. The values of _N_R and _N_F_R are explained
  231.      below:
  232.  
  233.      *   CCCCCCCCFFFFFFFFTTTT
  234.          _t_a_b_l_e: 2_n + _N_F REAL WORDS
  235.          _w_o_r_k: 2_n REAL WORDS
  236.  
  237.      *   ZZZZZZZZFFFFFFFFTTTT
  238.          _t_a_b_l_e: 2_n + _N_F DBL PREC WORDS
  239.          _w_o_r_k: 2_n DBL PREC WORDS
  240.  
  241.      *   CCCCCCCCFFFFFFFFTTTTMMMMRRRR
  242.          _t_a_b_l_e: 2_n + _N_F REAL WORDS
  243.          _w_o_r_k: 2_n REAL WORDS
  244.  
  245.      *   ZZZZZZZZFFFFFFFFTTTTMMMMRRRR
  246.          _t_a_b_l_e: 2_n + _N_F DBL PREC WORDS _w_o_r_k: 2_n DBL PREC WORDS
  247.  
  248.      *   CCCCCCCCFFFFFFFFTTTT2222DDDD _t_a_b_l_e: (2*_n_1+_N_F) + (2*_n_2+_N_F) REAL WORDS
  249.          _w_o_r_k: 2*MMMMAAAAXXXX((((_n_1,,,,_n_2)))) REAL WORDS
  250.  
  251.      *   ZZZZZZZZFFFFFFFFTTTT2222DDDD
  252.          _t_a_b_l_e: (2*_n_1+_N_F) + (2*_n_2+_N_F) DBL PREC WORDS _w_o_r_k: 2*MMMMAAAAXXXX((((_n_1,,,,_n_2)))) DBL
  253.          PREC WORDS
  254.  
  255.      *   CCCCCCCCFFFFFFFFTTTT3333DDDD _t_a_b_l_e: (2*_n_1+_N_F) + (2*_n_2+_N_F) + (2*_n_3+_N_F) REAL WORDS
  256.          _w_o_r_k: 2*MMMMAAAAXXXX((((_n_1,,,,_n_2,,,,_n_3)))) REAL WORDS
  257.  
  258.  
  259.  
  260.  
  261.                                                                         PPPPaaaaggggeeee 4444
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  269.  
  270.  
  271.  
  272.      *   ZZZZZZZZFFFFFFFFTTTT3333DDDD
  273.          _t_a_b_l_e: (2*_n_1+_N_F) + (2*_n_2+_N_F) + (2*_n_3+_N_F) DBL PREC WORDS
  274.          _w_o_r_k:  2*MMMMAAAAXXXX((((_n_1,,,,_n_2,,,,_n_3)))) DBL PREC WORDS
  275.  
  276.      *   CCCCCCCCFFFFFFFFTTTTMMMM
  277.          _t_a_b_l_e: (_N_F + 2 * _n) REAL WORDS
  278.          _w_o_r_k: 2_n REAL WORDS
  279.  
  280.      *   ZZZZZZZZFFFFFFFFTTTTMMMM
  281.          _t_a_b_l_e: (_N_F + 2 * _n) DBL PREC WORDS
  282.          _w_o_r_k: 2_n DBL PREC WORDS
  283.  
  284.      *   SSSSCCCCFFFFFFFFTTTT, CCCCSSSSFFFFFFFFTTTT
  285.          _t_a_b_l_e: (_n+_N_F_R) REAL WORDS
  286.          _w_o_r_k: _n+2 REAL WORDS
  287.  
  288.      *   DDDDZZZZFFFFFFFFTTTT, ZZZZDDDDFFFFFFFFTTTT
  289.          _t_a_b_l_e: (_n+_N_F_R) DBL PREC WORDS
  290.          _w_o_r_k: _n + 2 DBL PREC WORDS
  291.  
  292.      *   SSSSCCCCFFFFFFFFTTTT2222DDDD, CCCCSSSSFFFFFFFFTTTT2222DDDD
  293.          _t_a_b_l_e: (_n+_N_F_R) + (2*_n_2+_N_F) REAL WORDS
  294.          _w_o_r_k: _n_1+4*_n_2 REAL WORDS
  295.  
  296.      *   DDDDZZZZFFFFFFFFTTTT2222DDDD, ZZZZDDDDFFFFFFFFTTTT2222DDDD
  297.          _t_a_b_l_e: (_n_1+_N_F_R) + (2*_n_2+_N_F) DBL PREC WORDS
  298.          _w_o_r_k: _n_1 + 4 * _n_2 DBL PREC WORDS
  299.  
  300.      *   SSSSCCCCFFFFFFFFTTTT3333DDDD, CCCCSSSSFFFFFFFFTTTT3333DDDD
  301.          _t_a_b_l_e: (_n_1+_N_F_R) + (2*_n_2+_N_F) + (_2*_n_3+_N_F) REAL WORDS
  302.          _w_o_r_k: _n_1 + 4 * n3 REAL WORDS
  303.  
  304.      *   DDDDZZZZFFFFFFFFTTTT3333DDDD, ZZZZDDDDFFFFFFFFTTTT3333DDDD
  305.          _t_a_b_l_e: (_n_1+_N_F_R) + (2*_n_2+_N_F) + (2*_n_3+_N_F) DBL PREC WORDS
  306.          _w_o_r_k: _n_1 + 4 * n3 DBL PREC WORDS
  307.  
  308.      *   SSSSCCCCFFFFFFFFTTTTMMMM, CCCCSSSSFFFFFFFFTTTTMMMM
  309.          _t_a_b_l_e: (_n+_N_F_R) REAL WORDS
  310.          _w_o_r_k: _n + 2 REAL WORDS
  311.  
  312.      *   DDDDZZZZFFFFFFFFTTTTMMMM, ZZZZDDDDFFFFFFFFTTTTMMMM
  313.          _t_a_b_l_e: (_n+_N_F_R) DBL PREC WORDS
  314.          _w_o_r_k: _n + 2 DBL PREC WORDS
  315.  
  316.      The second area of difference is the _i_s_y_s parameter array, an array that
  317.      gives certain implementation-specific information.  All features and
  318.      functions of the FFT routines specific to any particular implementation
  319.      are confined to this _i_s_y_s array.  On any implementation, you can use the
  320.      default values by using an argument value of 0.
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.                                                                         PPPPaaaaggggeeee 5555
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  335.  
  336.  
  337.  
  338.      In the Origin series implementation, _i_s_y_s((((0000))))====0000 and _i_s_y_s((((0000))))=1 are
  339.      supported.  In SCSL versions prior to 1.3, only _i_s_y_s((((0000))))====0000 was allowed.
  340.      For _i_s_y_s((((0000))))====0000, _N_F====33330000 and _N_F_R====11115555, and for _i_s_y_s((((0000))))====1111, _N_F=_N_F_R=222255556666. The _N_F(_R)
  341.      words of storage in the table array contain a factorization of the length
  342.      of the transform.
  343.  
  344.      The smaller values of _N_F and _N_F_R for _i_s_y_s((((0000))))====0000 are historical.  They are
  345.      too small to store all the required factors for the highest performing
  346.      FFT, so when _i_s_y_s((((0000))))====0000, extra space is allocated when the table array is
  347.      initialized. To avoid memory leaks, this extra space must be deallocated
  348.      when the table array is no longer needed. The routines CCCCCCCCFFFFFFFFTTTTFFFF, CCCCCCCCFFFFFFFFTTTTMMMMFFFF,
  349.      etc., are used to release this memory.  Due to the potential for memory
  350.      leaks, the use of _i_s_y_s((((0000))))====0000 should be avoided.
  351.  
  352.      For _i_s_y_s((((0000))))====1111, the values of _N_F and _N_F_R are large enough so that no extra
  353.      memory needs to be allocated, and there is no need to call CCCCCCCCFFFFFFFFTTTTFFFF, etc.
  354.      to release memory. (If called, these routines will do nothing.)
  355.  
  356.      NOTE: _i_s_y_s((((0000)))) ==== 1111 means that _i_s_y_s is an integer array with two elements.
  357.      The second element, _i_s_y_s((((1111)))), will not be accessed.
  358.  
  359.      Finally, in addition to the _w_o_r_k array, the FFT routines also dynamically
  360.      allocate scratch space from the stack. The amount of space allocated can
  361.      be slightly bigger than the size of the largest processor cache. For
  362.      single processor runs, the default stack size is large enough that these
  363.      allocations generally cause no problems. But for parallel runs, you need
  364.      to ensure that the stack size of slave threads is big enough to hold this
  365.      scratch space. Failure to reserve sufficient stack space will cause
  366.      programs to dump core due to stack overflows.  The stack size of MP
  367.      library slave threads is controlled via the MMMMPPPP____SSSSLLLLAAAAVVVVEEEE____SSSSTTTTAAAACCCCKKKKSSSSIIIIZZZZEEEE
  368.      environment variable or the mmmmpppp____sssseeeetttt____ssssllllaaaavvvveeee____ssssttttaaaacccckkkkssssiiiizzzzeeee(((()))) library routine. See
  369.      the mmmmpppp(3C), mmmmpppp(3F) and ppppeeee____eeeennnnvvvviiiirrrroooonnnn(5) reference pages for more information
  370.      on controlling the slave stack size. For pthreads applications, the
  371.      thread's stack size is specified as one of many creation attributes
  372.      provided in the pthread_attr_t argument to pppptttthhhhrrrreeeeaaaadddd____ccccrrrreeeeaaaatttteeee(3P).  The
  373.      stacksize attribute should be set explicitly to a non-default value using
  374.      the pppptttthhhhrrrreeeeaaaadddd____aaaattttttttrrrr____sssseeeettttssssttttaaaacccckkkkssssiiiizzzzeeee(3P) call, described in the
  375.      pppptttthhhhrrrreeeeaaaadddd____aaaattttttttrrrr____iiiinnnniiiitttt(3P) man page.
  376.  
  377.    RRRReeeeaaaallll----ttttoooo----ccccoooommmmpppplllleeeexxxx FFFFFFFFTTTTssss
  378.      In the formulas on the man pages, there are _n real input values, and
  379.      _n/2+1 complex output values.  This property is characteristic of real-
  380.      to-complex FFTs.
  381.  
  382.      The mathematical definition of the Fourier transform takes a sequence of
  383.      _n complex values and transforms it to another sequence of _n complex
  384.      values.  A complex-to-complex FFT routine, such as CCCCCCCCFFFFFFFFTTTT or CCCCCCCCFFFFFFFFTTTTMMMM, will
  385.      take _n complex input values, and produce _n complex output values.  In
  386.      fact, one easy way to compute a real-to-complex FFT is to store the input
  387.      data, _x, in a complex array, then call routine CCCCCCCCFFFFFFFFTTTT to compute the FFT.
  388.      You get the same answer when using the SSSSCCCCFFFFFFFFTTTT/SSSSCCCCFFFFFFFFTTTTMMMM routine.
  389.  
  390.  
  391.  
  392.  
  393.                                                                         PPPPaaaaggggeeee 6666
  394.  
  395.  
  396.  
  397.  
  398.  
  399.  
  400. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  401.  
  402.  
  403.  
  404.      A separate real-to-complex FFT routine is more efficient. Because the
  405.      input data are real, you can make use of this fact to save almost half of
  406.      the computational work.  The theory of Fourier transforms tells us that
  407.      for real input data, you have to compute only the first _n/2 + 1 complex
  408.      output values, because the remaining values can be computed from the
  409.      first half of the values by the simple formula:
  410.  
  411.           _Y_K,_L = conjg(_Y_n-_k,_L) _f_o_r _n/_2 <= _k <= _n-1
  412.  
  413.      where the notation conjg(_Y) represents the complex conjugate of _y.
  414.  
  415.      In fact, in many applications, the second half of the complex output data
  416.      are never explicitly computed or stored.  Likewise, as explained later,
  417.      only the first half of the complex data has to be supplied for the
  418.      complex-to-real FFT.
  419.  
  420.      Another implication of FFT theory is that, for real input data, the first
  421.      output value, _Y(0), will always be a real number; therefore, the
  422.      imaginary part will always be 0.  If _n is an even number, _Y(_n/2) will
  423.      also be real and thus, have a zero imaginary part.
  424.  
  425.    CCCCoooommmmpppplllleeeexxxx----ttttoooo----rrrreeeeaaaallll FFFFFFFFTTTTssss
  426.      Consider the complex-to-real case.  The effect of the computation is
  427.      given by the formulas on the man pages, but with _X complex and _Y real.
  428.  
  429.      In general, the FFT transforms a complex sequence into a complex
  430.      sequence; however, in a certain application you may know the output
  431.      sequence is real, perhaps because the complex input sequence was the
  432.      transform of a real sequence.  In this case, you can save about half of
  433.      the computational work.
  434.  
  435.      According to the theory of Fourier transforms, for the output sequence,
  436.      _Y, to be a real sequence, the following identity on the input sequence,
  437.      _X, must be true:
  438.  
  439.           _X_k,_L = conjg(_X_n-_k,_L)
  440.  
  441.           for _n/2 <= _k <= _n-1
  442.  
  443.      And, in fact, the following input values
  444.  
  445.           _X_k,_L for _k > _n/2
  446.  
  447.      do not have to be supplied, because they can be inferred from the first
  448.      half of the input.
  449.  
  450.      Thus, in the complex-to-real routine, CCCCSSSSFFFFFFFFTTTTMMMM, the arrays can be
  451.      dimensioned as follows:
  452.  
  453.           Fortran:
  454.  
  455.                COMPLEX X(0:ldx-1, 0:lot-1)
  456.  
  457.  
  458.  
  459.                                                                         PPPPaaaaggggeeee 7777
  460.  
  461.  
  462.  
  463.  
  464.  
  465.  
  466. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  467.  
  468.  
  469.  
  470.                REAL    Y(0:ldy-1, 0:lot-1)
  471.  
  472.  
  473.           C/C++:
  474.  
  475.                scsl_complex x[lot][ldx];
  476.                float        y[lot][ldy];
  477.  
  478.  
  479.           C++ STL:
  480.  
  481.                complex<float> x[lot][ldx];
  482.                float          y[lot][ldy];
  483.  
  484.  
  485.           where _l_d_x >= _n/2 + 1, _l_d_y >= _n.
  486.  
  487.           In each column, there are (_n/2) + 1 complex input values and _n real
  488.           output values.  Even though only (_n/2) + 1 input values are
  489.           supplied, the size of the transform is still _n in this case, because
  490.           implicitly the FFT formula for a sequence of length _n is used.
  491.  
  492.           Another implication of the theory is that _X(0, _L) must be a real
  493.           number (that is, must have zero imaginary part).  If _n is an even
  494.           number, _X(_n/2, _L) must also be real.  The CCCCSSSSFFFFFFFFTTTTMMMM and CCCCSSSSFFFFFFFFTTTT routines
  495.           assume that each of these values is real; if a nonzero imaginary
  496.           part is given, it is ignored.
  497.  
  498.    IIIInnnniiiittttiiiiaaaalllliiiizzzzaaaattttiiiioooonnnn
  499.      The _t_a_b_l_e array stores the trigonometric tables used in calculation of
  500.      the FFT.  You must initialize _t_a_b_l_e by calling the routine with _i_s_i_g_n = 0
  501.      prior to doing the transforms.  If the value of the problem size, _n, does
  502.      not change, _t_a_b_l_e does not have to be reinitialized.
  503.  
  504.      Because SSSSCCCCFFFFFFFFTTTT and CCCCSSSSFFFFFFFFTTTT use the same format for _t_a_b_l_e, either can be used
  505.      to initialize it (note that CCCCCCCCFFFFFFFFTTTT uses a different table format).
  506.  
  507.    DDDDiiiimmmmeeeennnnssssiiiioooonnnnssss
  508.      In the preceding descriptions and on the specific man pages, it is
  509.      assumed that array subscripts were zero-based, as is customary in FFT
  510.      applications.  However, if you prefer to use the more customary Fortran
  511.      style with subscripts starting at 1 you do not have to change the calling
  512.      sequence.
  513.  
  514.      -------------------------------------------------------------------------
  515.        Routine       subscripts starting at 0       subscripts starting at 1
  516.      -------------------------------------------------------------------------
  517.        CCFFT         COMPLEX X(0:N-1)              COMPLEX X(N)
  518.                      COMPLEX Y(0:N-1)              COMPLEX Y(N)
  519.        CCFFT2D       COMPLEX X(0:ldx-1, 0:n2-1)    REAL    X(ldx, n2)
  520.                      COMPLEX Y(0:ldy-1, 0:n2-1)    COMPLEX Y(ldy, n2)
  521.        SCFFT         REAL    X(0:n-1)              REAL    X(n)
  522.  
  523.  
  524.  
  525.                                                                         PPPPaaaaggggeeee 8888
  526.  
  527.  
  528.  
  529.  
  530.  
  531.  
  532. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  533.  
  534.  
  535.  
  536.                      COMPLEX Y(0:n/2)              COMPLEX Y(n/2 + 1)
  537.        SCFFT2D       REAL    X(0:ldx-1, 0:n2-1)    COMPLEX X(ldx, n2)
  538.                      COMPLEX Y(0:ldy-1, 0:n2-1)    COMPLEX Y(ldy, n2)
  539.        CCFFTM        COMPLEX X(0:ldx-1, 0:lot-1)   COMPLEX X(ldx, lot)
  540.                      COMPLEX Y(0:ldy-1, 0:lot-1)   COMPLEX Y(ldy, lot)
  541.        CCFFTMR       COMPLEX X(0:ldx-1, 0:n-1)     COMPLEX X(ldx, n)
  542.                      COMPLEX Y(0:ldy-1, 0:n-1)     COMPLEX Y(ldy, n)
  543.      -------------------------------------------------------------------------
  544.  
  545.  
  546. CCCCoooonnnnvvvvoooolllluuuuttttiiiioooonnnn aaaannnndddd CCCCoooorrrrrrrreeeellllaaaattttiiiioooonnnn RRRRoooouuuuttttiiiinnnneeeessss
  547.      These routines feature convolution for Finite Impulse Response (FIR) as
  548.      well as correlations. Each of these routines is highly optimized for
  549.      single-processor use. The routines which use two-dimensional input
  550.      sequences are multitasked (multi-threaded).
  551.  
  552.      The convolution and correlation routines are very general. To achieve
  553.      this generality and maximum flexibility, one-dimensional sequences are
  554.      defined by 3 parameters. Six parameters are necessary for two-dimensional
  555.      sequences.  One drawback of this generality are the long calling
  556.      sequences.
  557.  
  558.      The following table contains a summary of the filter and correlation
  559.      routines. Each routine has its own man page.  In this table, rows of the
  560.      table represent data types for the routines in each column:
  561.  
  562.      *   CCCC implies 32-bit complex data.
  563.  
  564.      *   ZZZZ implies 64-bit double complex data.
  565.  
  566.      *   SSSS implies 32-bit real data.
  567.  
  568.      *   DDDD implies 64-bit double precision real data.
  569.  
  570.      Columns of the table represent the type of computation as well as the
  571.      number of dimensions for which the convolution or correlation is
  572.      calculated for the routines in each row:
  573.  
  574.      *   One-dimensional FIR applies a Finite Impulse Response filter to one-
  575.          dimensional signals.
  576.  
  577.      *   One-dimensional (multiple) FIR applies a Finite Impulse Response
  578.          filter to multiple one-dimensional signals.
  579.  
  580.      *   Two-dimensional FIR applies a Finite Impulse Response filter to two-
  581.          dimensional signals.
  582.  
  583.      *   One-dimensional COR calculates the correlation of one-dimensional
  584.          sequences.
  585.  
  586.  
  587.  
  588.  
  589.  
  590.  
  591.                                                                         PPPPaaaaggggeeee 9999
  592.  
  593.  
  594.  
  595.  
  596.  
  597.  
  598. IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))                                                    IIIINNNNTTTTRRRROOOO____FFFFFFFFTTTT((((3333SSSS))))
  599.  
  600.  
  601.  
  602.      *   One-dimensional (multiple) COR calculates the correlation of multiple
  603.          one-dimensional sequences.
  604.  
  605.      *   Two-dimensional COR calculates the correlation of two-dimensional
  606.          sequences.
  607.  
  608.      ------------------------------------------------------------
  609.           Type       1D (single)    1D (multiple)         2D
  610.      ------------------------------------------------------------
  611.            C            CFIR1D         CFIRM1D          CFIR2D
  612.            Z            ZFIR1D         ZFIRM1D          ZFIR2D
  613.            S            SFIR1D         SFIRM1D          SFIR2D
  614.            D            DFIR1D         DFIRM1D          DFIR2D
  615.      ------------------------------------------------------------
  616.            C            CCOR1D         CCORM1D          CCOR2D
  617.            Z            ZCOR1D         ZCORM1D          ZCOR2D
  618.            S            SCOR1D         SCORM1D          SCOR2D
  619.            D            DCOR1D         DCORM1D          DCOR2D
  620.      ------------------------------------------------------------
  621.  
  622.  
  623. SSSSEEEEEEEE AAAALLLLSSSSOOOO
  624.      IIIINNNNTTTTRRRROOOO____SSSSCCCCSSSSLLLL(3S)
  625.  
  626.  
  627.  
  628.  
  629.  
  630.  
  631.  
  632.  
  633.  
  634.  
  635.  
  636.  
  637.  
  638.  
  639.  
  640.  
  641.  
  642.  
  643.  
  644.  
  645.  
  646.  
  647.  
  648.  
  649.  
  650.  
  651.  
  652.  
  653.  
  654.                                                                        PPPPaaaaggggeeee 11110000
  655.  
  656.  
  657.  
  658.  
  659.  
  660.  
  661.